perm filename LOCUS[00,BGB] blob
sn#115976 filedate 1974-08-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00015 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 {≤G⊂CαLOCUS SOLVING.λ30P90I425,0JCFA} SECTION 9.
C00006 00003 ⊂9.1 An Eight Parameter Camera Model.⊃
C00008 00004
C00010 00005
C00011 00006
C00012 00007 {QW0,1260,0,1900I200,0}⊂9.2 Camera Locus Solving: One View of Three Points⊃
C00015 00008 {W0,750,100,1900λ25JUFA}
C00020 00009
C00024 00010
C00027 00011
C00029 00012
C00032 00013 ⊂9.3 Object Locus Solving: Silhouette Cone Intersection.⊃
C00034 00014 ⊂9.4 Sun Locus Solving: A Simple Solar Emphemeris.⊃
C00037 00015 ⊂9.5 Related and Future Locus Solving Work.⊃
C00039 ENDMK
C⊗;
{≤G;⊂C;αLOCUS SOLVING.;λ30;P90;I425,0;JCFA} SECTION 9.
{JCFD} CAMERA AND FEATURE LOCUS SOLVING.
{λ10;W250;JAFA}
9.0 Introduction to Locus Solving.
9.1 An Eight Parameter Camera Model.
9.2 Camera Locus Solving: One View of Three Points.
9.3 Object Locus Solving: Silhouette Cone Intersection.
9.4 Sun Locus Solving: A Simple Solar Emphemeris.
9.5 Related and Future Locus Solving Work.
{λ30;W0;I950,0;JUFA}
⊂9.0 Introduction to Locus Solving.⊃
There are three kinds of locus solving problems in computer
vision: camera locus solving, feature locus solving and sun locus
solving. Camera solving is routinely attempted in two ways: using one
image the 2-D image loci of a set of already known 3-D world loci
(perhaps points on a calibration object) are measured and a camera
model is computed; or using two or more images a set of corresponding
landmark feature points are found among the images and the whole
system is solved relative to itself. After the camera positions are
known, the location and extent of the objects composing the scene can
be found using parallax (motion parallax and stereo parallax).
Parallax is the principal means of depth perception and is the
alchemist for converting 2-D images into 3-D models. After the camera
and object positions are known to some accuracy, the nature and
location of light sources might potentially be deduced from the
shines and shadows in the images. However, in outdoor situations the
primary light source is the sun, whoes position in the sky can be
computed from the time, date, latitude and longitude by means of a
simple emphemeris routine.{Q}
⊂9.1 An Eight Parameter Camera Model.⊃
In GEOMED and CRE the basic camera model is specified by
eight parameters. There are three parameters for the lens center
location of the camera: CX, CY, CZ; three parameters for the
orientation: WX, WY, WZ; and two parameters for the projection
ratios, the aspect ratio: AR; and the focal ratio: FR. The location
is given in world coordiates. The direction of the orientation vector
specifies an axis and its magnitude a rotation which when applied to
a set of three axes unit vectors yeilds a set of unit vectors that
determines the camera coordinate system. By convention the principle
ray of the camera is parallel to the Z axis unit vector and is
negatively directed. The camera raster is alligned such that the rows
(vidicon scan lines) are parallel to the X unit vector and the
columns are parallel to the Y unit vector.
The aspect ratio is the ratio of height to width of a single
vidicon sample point called a pixel. The aspect ration is always
approximately one. The focal ratio is the ratio of the focal plane
distance to the width of a single pixel. The focal ratio is typically
around one thousand.
The actual physical size of the digital raster of a
television vidicon is on the order of 12 milimeters wide by 8
millimeters high with approxiately 512 lines of potentially 512
sample. However, standard televisions scan in two phases so that the
computer A pixel rectangle is aprroxiaately 40 microns by 40 microns.
Related to the basic eight parameters is the fiction that the
physical dimensions of a vidicon pixel: PDX, PDY, PDZ
are approximately 40 by 40 by 40 microns.
By constrast, the cones and rods in a human
eye are 1 and 2 microns in diameter respectively.
Logical Image Size LDX LDY LDZ
Focal Plane Distance FOCAL
~Lens Center Irrelevancy Theorem~.
The actual location of the principal axis of the lens in the
image plane is irrelevant because the effect of deviation from the
true center is equivalent to rotating the camera.
~Spatial Resolution~
~Depth Ambiguity and Parallax Horizon~
Given two television cameras
separated by a distance 2*D mounted side by side
(that is pointed in almost the same direction with
principle axes orthogonal to the separation vector).
≤D≥R Depth Ambiguity
R Range
D Half distance of camera separation
PD Pixel Diameter
FOCAL Focal Plane Distance
TAN(≤a≥) = PD/FOCAL
TAN(≤b≥) = RANGE/D
TAN(≤a≥+≤b≥) = (≤D≥R + R)/D =
{Q;W0,1260,0,1900;I200,0;}⊂9.2 Camera Locus Solving: One View of Three Points⊃
{FC} - The Iron Triangle Camera Solving Method.{FA;λ30;}
A mobile robot having only visual perception must determine
where it is going by what it sees. Specifically, the position of the
robot is found relative to the position of the lens center of its
camera. The following algorithm is a geometric method for computing
the locus of a camera's lens center from three landmark points.
{I∂500,0;}
Consider four non-coplanar points A, B, C and L. Let L be
the unknown camera's lens center, here after to be called the camera
locus, also let A, B and C be the landmark points whoes loci either
are given on a map or are found by stereo from two already known
viewing positions. Assuming for the moment an ideal camera which can
see all 4π steradians at once, the camera can measure the angles
formed by the rays from the camera locus to the landmark points. Let
these angles be called ≤a≥, ≤b≥ and ≤g≥ where ≤a≥ is the angle BLC,
≤b≥ is the angle ALC and ≤g≥ is the angle ALB. The camera also
measures whether the landmarks appear to be in clockwise or counter
clockwise order as seen from L. If the landmarks are counterclockwise
then B is swaped with C and ≤b≥ with ≤g≥. A mechanical analog of the
problem would be to position a rigid triangular piece of sheet metal
between the legs of a tripod so that its corners touch each leg. The
metal triangle is the same size as the triangle ABC and the legs of
the tripod are rigidly held forming the angles ≤a≥, ≤b≥ and ≤g≥. The
algorithm was developed by thinking in terms of this analogy.
{L100,130;H3;X0.8;*IRONT.PLT;FD;
L100,130;I∂80,∂-280;}A{
L100,130;I∂-225,∂-130;}B{
L100,130;I∂270,∂-110;}C{
L100,130;I∂0,∂410;}L{
W0,1260,100,1800;FA;Q;λ10;}
{W0,750,100,1900;λ25;JUFA}
\In order to put the iron triangle
into the tripod, the edge BC is first placed
between the tripod legs of angle ≤a≥. Let
a be the length of BC, likewise b and c
are the lengths of AC and AB.
\Restricting attention to the plane LBC,
consider the locus of points L' arrived at
by sliding the tripod and maintaining
contacts at B and C.
\Remembering that in a circle, a chord
subtends equal angles at all points of each
arc on either side of the chord; it can be seen
that the set of possible L' points lie
on a circular arc. Let this arc be called L's arc, which is part of L's
circle.
\Also in a circle the angle at the center
is double the angle at the
circumference, when the rays forming the
angles meet the circumference in the
same two points.
\And the perpendicular bisector of a
chord passes thru the center of the
chord's circle bisecting the central
angle. Let S be the distance between the
center of the circle and the chord BC.
So by trigonometric definitions:
{JC} R = a / 2sin(≤a≥)
{JC} S = R cos(≤a≥)
{H3;
L560,700;C5;I∂10,∂20;}L{I∂0,∂-120;}≤a≥{L560-320,690;}a{
L560,700,560-350,700+94;
L560,700,560-350,700-94;
L560,700;C50,165*π/180,30*π/180;
L400-138,700+80;C5;I∂-10,∂-5;}B{
L400-138,700-80;C5;I∂30,∂-5;}C{
L400-138,700+80,400-138,700-80;
L560,400;C5;I∂10,∂20;}L{I∂0,∂-120;}≤a≥{L560-320,390;}a{
L560,400,560-350,400+94;
L560,400,560-350,400-94;
L560,400;C50,165*π/180,30*π/180;
L400-138,400+80;C5;I∂-10,∂-5;}B{
L400-138,400-80;C5;I∂30,∂-5;}C{
L400-138,400+80,400-138,400-80;
L502,522;C5;I∂0,∂10;}L'{
L502-70,522-35;}≤a≥{
L502,522;C50,190*π/180,30*π/180;
L502,522,502-345,522-60;
L502,522,502-268,522-225;
L560,100;C5;I∂10,∂20;}L{I∂0,∂-120;}≤a≥{L560-315,90;}a{
L560,100,560-350,100+94;
L560,100,560-350,100-94;
L560,100;C50,165*π/180,30*π/180;
L400-138,100+80;C5;I∂-10,∂-10;}B{
L400-138,100-80;C5;I∂30,∂-10;}C{
L400-138,100+80,400-138,100-80;
L502,222;C5;I∂0,∂10;}L'{
L502-70,222-35;}≤a≥{
L502,222;C50,190*π/180,30*π/180;
L502,222,502-345,222-60;
L502,222,502-268,222-225;
L400,100;C160;
L400,-300;C160;C5;
C50,150*π/180,60*π/180;I∂10,∂-90;}2≤a≥{
L400,-300,400-138,-300+80;
L400,-300,400-138,-300-80;
L560,-300;C5;I∂10,∂20;}L{I∂0,∂-120;}≤a≥{L560-315,-310;}a{
L560,-300,560-350,-300+94;
L560,-300,560-350,-300-94;
L560,-300;C50,165*π/180,30*π/180;
L400-138,-300+80;C5;I∂-10,∂-10;}B{
L400-138,-300-80;C5;I∂30,∂-10;}C{
L400-138,-300+80,400-138,-300-80;
L400,-700;C160,-150*π/180,300*π/180;C5;
L400-80,-700-30;}S{
L400-80,-700+50;}R{
L400-190,-700+25;}a/2{
L400,-700;
C50,150*π/180,30*π/180;I∂-10,∂-75;}≤a≥{
L400-138,-700+80;C5;I∂-10,∂-10;}B{
L400-138,-700-80;C5;I∂30,∂-10;}C{
L400-138,-700-80,400-138,-700+80,400,-700;
L400-138,-700,400+160,-700;
W0,1260,100,1800;λ30;Q}
The position of L on its arc in the plane BLC can be expressed in
terms of one parametric variable omega ≤w≥, where ≤w≥ is the counter
clockwise angular displacement of L from the perpendicular
bisector such that for ≤w≥=π-≤a≥ L is at B and for ≤w≥=≤a≥-π L is at C.
By spinning the iron triangle about the axis BC, the vertex A sweeps
a circle
Let H be the radius of A's circle and let D be the directed
distance between te center of A's circle and the midpoint of BC.
By Trigonometric relations on the triangle ABC:
cos(ACB) = (a↑2 + b↑2 - c↑2)/2ab
sin(ACB) = sqrt(1 - cos(C)↑2)
H = b sin(ACB)
D = b cos(ACB) - a/2
Now consider the third leg of the tripod which forms the angles ≤b≥
and ≤g≥. The third leg intersects the BLC plane at point L and
extends into the appropriate halfspace so that the landmark
points appear to be in clockwise order as seen from L. Let A' be
the third leg's point of intersection with the plane containing
A's circle.
Let the distance between the point A' and the center of A's
circle less the radius H of A's circle be called "The Gap". The
gap's value is negative if A' falls within A's circle.
By constructing an expression for the value of the Gap as a
function of the parametric variable ≤w≥, a root solving routine can
find the ≤w≥ for which the gap is zero thus determining the
orientation of the triangle with respect to the tripod and in
turn the locus of the point L in space.
Using vector geometry, place an origin at the midpoint of BC,
establish the unit y-vector j pointing towards the vertex B, let the
plane BCL be the x-y plane and orient the unit x-vector i pointing
into L's halfplane. For right handedness, set the unit z-vector k to
i cross j. In the newly defined coordinates points B, C, and L become
the vectors:{JV;λ10;}
B = (-s, +a/2, 0);
C = (-s, -a/2, 0)
L = (R cos(w), R sin(w), 0)
Introducing two unknowns xx and zz the locus of point A' as a vector is:
A' = (xx, D, zz)
The vectors corresponding to the legs of the tripod are:
LB = B - L = (-s-Rcos(w), +a/2-Rsin(w), 0)
LC = C - L = (-s-Rcos(w), -a/2-Rsin(w), 0)
LA = A'- L = (xx-Rcos(w), D-Rsin(w), zz)
Since the third leg forms the angles ≤b≥ and ≤g≥:
LA . LC = |LA| |LC| cos(≤b≥)
LA . LB = |LA| |LB| cos(≤g≥)
Solving each equation for |LA| yields:
|LA| = (LA . LC)/|LC|cos(≤b≥) = (LA . LB)/|LB|cos(≤g≥)
Multiplying by |LB| |LC| cos (≤b≥) cos (≤g≥) gives:
(LA . LC)|LB| cos(≤g≥) = (LA . LB)|LC| cos(≤b≥)
Expressing the vector quantites in terms of their components:
|LB| = sqrt((-S-Rcos(w))↑2 + (+a/2-Rsin(w))↑2)
|LC| = sqrt((-S-Rcos(w))↑2 + (-a/2-Rsin(w))↑2)
LA . LC = (xx-Rcos(w))(-s-Rocs(w)) + (D-Rsin(w))(-a/2-Rsin(w))
LA . LC = (xx-Rcos(w))(-s-Rocs(w)) + (D-Rsin(w))(+a/2-Rsin(w))
Substituting:
((xx-Rcos(w))(-s-Rcos(w)) + (D-Rsin(w))(-a/2-Rsin(w))) |LB|cos(≤g≥)
= ((xx-Rcos(w))(-s-Rcos(w)) + (D-Rsin(w))(+a/2-Rsin(w))) |LC|cos(≤b≥)
The previous equation is linear in xx, so solving for xx:
xx = P/Q + Rcos(w)
where
P = (-s-Rcos(w))(|LB|cos(≤g≥) - |LC|cos(≤b≥))
Q = (D-Rsin(w))((+a/2-Rsin(w))|LC|cos(≤b≥)
- (-a/2-Rsin(w))|LB|cos(≤g≥))
The unknown zz can be found from the definition of |LA|
|LA| = sqrt( (xx-Rcos(w))↑2 + (D-Rsin(w))↑2 + zz↑2)
so zz = sqrt( |LA|↑2 - (P/Q)↑2 - (D-Rsin(w))↑2)
and since:
|LA| = (LA . LC) / |LC|cos(≤b≥)
The negative values of zz are precluded by the clockwise ordering
of the landmark points. Thus the expression for the Gap can be
formed:
GAP = sqrt( (XX+S)↑2 + zz↑2 ) - H
As mentioned above, when the gap is zero the problem is solved
since the locus of A' then must be on A's circle, so the triangle
touches the third leg. The gap function looks like a cubic on its
interval [≤a≥-π,π-≤a≥] which almost always has just one zero crossing.
Having found the locus of L in the specially defined coordinate
system all that remains to do is to solve for the components of L
in the coordinate system that A, B and C were given. This is
may be done by considering three vector expressions which are not
dependent on the frame of reference and do not have second order
L terms, namely: (CA dot CL); (CB dot CL); and ((CA x CB) dot CL).
Let the locus of L in the given frame of reference be (X,Y,Z) and
let the components of the points A, B and C be (XA,YA,ZA),
(XB,YB,ZB) and (XC,YC,ZC) respectively. Listing all four points in
both frames of reference:{λ10;JA}
A = (xx, D, zz) = (XA, YA, ZA)
B = (-s, +a/2, 0) = (XB, YA, ZA)
C = (-s, -a/2, 0) = (XC, YC, ZC)
L = (Rcos(w),Rsin(w),0) = ( X, Y, Z)
Evaluating the vector expressions which are invariant:
CA = A - C = (XA-XC. YA-YC, ZA-ZC)
CB = B - C = (0, a, 0) = (XB-XC, YB-YC, ZB-ZC)
CL = L - C = (Rcos(w)+s,Rsin(w)+a/2,0) = ( X-XC, Y-YC, Z-ZC)
CA . CL = (xx+S)(Rcos(w)+s)+(D+a/2)(Rsin(w)+A/2)
= (XA-XC)(X-XC) + (YA-YC)(Y-YC) + (ZA-ZC)(Z-ZC)
CB . CL = a(Rsin(w) + a/2)
= (XB-XC)(X-XC) + (YB-YC)(Y-YC) + (ZB-ZC)(Z-ZC)
(CA x CB) . CL = -a zz(Rcos(w) + s)
= ((YA-YC)(ZB-ZC) - (ZA-ZC)(YB-YC)) (X-XC)
- ((XA-XC)(ZB-ZC) - (ZA-ZC)(XB-XC)) (Y-YC)
+ ((XA-XC)(YB-YC) - (YA-YC)(XB-XC)) (Z-ZC)
The last three equations are linear equations in the three
unknowns X, Y & Z which are readily isolated by Cramer's Rule.
⊂9.3 Object Locus Solving: Silhouette Cone Intersection.⊃
The silhouette cone intersection method is
a simple (nearly obvious) form of wide angle, stereo contruction.
The idea arose out of an original intention to do "blob" oriented,
however a 2-D blob came to be represented by a silhouette polygon and
a 3-D blob consquently came to be represented by a polyhedron.
The present implementation requires a very favorably arranged viewing
environment (white objects on dark backgrounds)
although application to more natural situations would be possible
if the necessary hardware were built for extracting
depth discontinuity edges by bulk correlation.
After the camera location, orientation and projection are know;
3-D object models can be constructed.
⊂9.4 Sun Locus Solving: A Simple Solar Emphemeris.⊃
The location of the sun is useful to a robot vehicle vision
system both for sophisticated scene intrepretation and for avoiding
the blunder of burning holes in the television vidicon. The
approximate position of the sun in the sky is readily computed from
the time, date, latitude and longitude using circular approximations.
{λ10;JAF3;}
PROCEDURE SUNLOCUS (REAL DAY,TIME,LAT,LONG; REFERENCE REAL SUNAZM,SUNALT);
BEGIN
REAL RHO,PHI,TMP,ECLIPTIC;
COMMENT POSITION OF THE SUN ON THE ECLIPTIC IN THE CELESTIAL SPHERE;
ECLIPTIC← ((23+27/60)*PI);
RHO ← 2*PI*DAY/365.25
EAST ← SIN(RHO)*COS(ECLIPTIC);
NORTH ← SIN(RHO)*SIN(ECLIPTIC);
ZENITH ← COS(RHO);
COMMENT LOCAL MERIDIAN OF LONGITUDE;
COMMENT LOCAL SOLAR TIME = (24 HOUR PACIFIC STANDARD TIME - 8 MINUTES 44 SECONDS);
PHI ← PI*(1-TIME/12) - ATAN2(EAST,ZENITH);
TMP ← ZENTITH*COS(PHI) - SIN(PHI)*EAST;
EAST ← EAST*COS(PHI) + SIN(PHI)*ZENITH;
ZENITH ← TMP;
COMMENT ROTATE CLOCKWISE IN THE NORTH/ZENITH PLANE TO LOCAL LATITUDE;
TMP ← COS(LAT)*ZENITH + SIN(LAT)*NORTH;
NORTH ← COS(LAT)*NORTH - SIN(LAT)*ZENITH;
ZENITH ← TMP;
CONVERT TO ANGULAR MEASURES;
SUNAZM ← ATAN2(NORTH,EAST);
SUNALT ← PI/2 - AOCS(ZENTIH);
END "SUNLOCUS";
{λ30;JUFA;}
⊂9.5 Related and Future Locus Solving Work.⊃
Although the bulk of this chapter concerned camera solving
using one view of three points the multi view camera calibration is
probably more important to continous image processing but I have very
little to contribute at this time to the existing collection of hill
climbing error minimizing methods.
I have always disliked the multi dimensional hill climber approach
and have sought a more geometric and intuitive solution to the
problem; so far I have only turned up a hill climber in fewer
dimensions (three degrees of freedom) involving six tonged forks
which are rotated about iron circle in two planes Orbiting forks
sweep out families of hyperbolic sheets which leaves one with a set
of contrainted second order equations in one parameter, which might
yet have a closed form anayltic solution.